package com.kjc.demo.basic.algorithmtest;

public class Test0925 {
	
	/**
	 * 	冒泡排序
	 * */
	public void bubbleSort(int[] arr) {
		for(int i = 0 ; i < arr.length - 1; i++) {
			for(int j=0 ; j <arr.length - i -1;j++) {
				if(arr[j] > arr[j+1]) {
					int temp = arr[j];
					arr[j] = arr[j+1];
					arr[j+1] = temp;
				}
			}
		}
	}
	
	/**
	 * 	选择排序
	 * */
	public void selectSort(int[] arr) {
		for(int i=0 ; i< arr.length-1;i++) {
			int min = i;
			for(int j = i + 1; j < arr.length -1;j++) {
				if(arr[min] > arr[j]) {
					min = j;
				}
			}
			if(min != i) {
				int temp = arr[min];
				arr[min] = arr[i];
				arr[i] = temp;
			}
		}
	}
	
	/**
	 * 	插入排序
	 * */
	public void insertSort(int[] arr) {
		for(int i=1; i < arr.length ;i ++) {
			if(arr[i] < arr[i-1]) {
				int j = i;
				while(j > 0 && arr[j] < arr[j-1]) {
					int temp = arr[j];
					arr[j] = arr[j-1];
					arr[j-1] = temp;
					j--;
				}
			}
		}
	}
	
	/**
	 * 	快速排序
	 * */
	public void quickSort(int arr[],int left,int right) {
		int i=left;
		int j = right;
		int pre = arr[left];
		while(i < j) {
			while(i < j && arr[j] > pre) {
				j--;
			}
			while(i< j && arr[i] < pre) {
				i++;
			}
			
			if(i< j && arr[i] == arr[j]) {
				i++;
			}else {
				int temp = arr[i];
				arr[i] = arr[j];
				arr[j] = temp;
			}
		}
		if(i-1 > left) {
			quickSort(arr,left,i-1);
		}
		if(i+1 < right) {
			quickSort(arr,i+1,right);
		}
		
	}
	
	/**
	 * 	希尔排序
	 * */
	public void shellSort(int[] arr) {
		for(int gap= arr.length/2 ;gap > 0;gap=gap/2) {
			for(int i = gap;gap< arr.length;i++) {
				int j = i;
				while(j-gap >= 0 && arr[j] < arr[j-gap]) {
					int temp = arr[j];
					arr[j] = arr[j-gap];
					arr[j-gap] = temp;
					j= j-gap;
				}
			}
		}
	}
	
}
